package leetCode;

public class T459 {
    public static void main(String[] args) {

        System.out.println(new SolutionT459().repeatedSubstringPattern("aba"));
    }
}
class SolutionT459 {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = next(s);
        if (next[s.length()-1]>0&&s.length()%(s.length()-next[s.length()-1])==0){
            return true;
        }
        return false;
    }


    public int[]next(String needle){
        int[]next=new int[needle.length()];
        char[] charArrayChars = needle.toCharArray();
        int j=0;
        next[0]=0;
        for (int i=1;i<needle.length();i++){
            while (j>0&&charArrayChars[i]!=charArrayChars[j]){
                j=next[j-1];
            }
            if (charArrayChars[i]==charArrayChars[j]){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}